package com.lw.leetcode.back.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * back
 * 329. 矩阵中的最长递增路径
 * 剑指 Offer II 112. 最长递增路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/2 11:53
 */
public class LongestIncreasingPath {

    public static void main(String[] args) {
        LongestIncreasingPath test = new LongestIncreasingPath();
        int[][] arr = Utils.getArr(200, 200, 0, 1000000000);

        int i = test.longestIncreasingPath(arr);
        System.out.println(i);
    }

    private int[][] matrix;
    private int[][] arr;
    private int m;
    private int n;
    private int[][] counts = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.arr = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, find(i, j, -1));

            }
        }
        return max;
    }

    private int find(int x, int y, int value) {
        if (x < 0 || x == m || y < 0 || y == n || matrix[x][y] <= value) {
            return 0;
        }
        if (arr[x][y] != 0) {
            return arr[x][y];
        }
        int max = 0;
        int v = this.matrix[x][y];
        for (int[] count : counts) {
            max = Math.max(max, find(x + count[0], y + count[1], v));
        }
        max++;
        arr[x][y] = max;
        return max;
    }


}
